package com.str.HT;

import com.str.map.Map;

public class CBHT implements Map {

  // An object of class CBHT is a closed-bucket hash table, containing
  // entries of class Entry.

// Inner class
  private static class Entry {

    // Each ArrayMap.Entry object is a map entry consisting of a key,
    // which is a Comparable object, and a value, which is an arbitrary
    // object.
    Object key;
    Object value;
    Entry next;

    Entry(Object k, Object v, Entry n) {
      key = k;
      value = v;
      next = n;
    }
    	
    public String toString()
    { return "<" + key + "," + value + ">";	}
  }

  private static final int DEFAULT_SIZE = 23;
  private static final double MAX_LOAD_FACTOR = 0.75;
  private Entry[] array;
  private int count;

// Constructors
  public CBHT()
  { this(DEFAULT_SIZE); }
  
  public CBHT(int m) { 
  // Construct an empty CBHT with m array.
    array = new Entry[m];
    count = 0;
  }  

// Modifiers
  public void clear() {
  	for (int i = 0; i < array.length; i++)
  	  array[i] = null;
  	count = 0;
  }

  public void add(Object key, Object val) {
  // Insert the entry <key, val> into this CBHT.
    int home = hash(key);
    for (Entry curr = array[home]; curr != null; curr = curr.next)
      if (key.equals(curr.key)) {
        curr.value = val;
        return;
      }
    // Insert newEntry at the front of the 1WLL in bucket b ...
    array[home] = new Entry(key, val, array[home]);
    if (++count > array.length * MAX_LOAD_FACTOR)
  	  expand(); 
  }   

  public Object remove(Object key) {
  // Delete the entry (if any) whose key is equal to key from this CBHT.
    int home = hash(key);
    for (Entry prior = null, curr = array[home];
        curr != null;
        prior = curr, curr = curr.next) {
      if (key.equals(curr.key)) {
      	Object temp = curr;
        if (prior == null)
          array[home] = curr.next;
        else
          prior.next = curr.next;
        count--;
        return temp;
      }
    }
    return null;
  }

// Accessors  
  public boolean isEmpty()
  { return count == 0; }

  public int size() 
  { return count; }
  
  public Object getValue(Object key) {
  // Find which if any node of this CBHT contains an entry whose key is equal 
  // to targetKey. Return a link to that node (or null if there is none).
    int home = hash(key);
    for (Entry curr = array[home]; curr != null; curr = curr.next)
      if (key.equals(curr.key))
        return curr.value;
    return null;
  }
  
// Auxiliary method  
  private int hash(Object key) {
  // Translate key to an index of the array array.
    return Math.abs(key.hashCode()) % array.length;
  }
    
  private void expand() { 	
    Entry[] oldArray = array;
    int oldSize = array.length;
	int newSize = nextPrime(2 * oldSize);
	array = new Entry[newSize];
    count = 0;
  	for (int i = 0; i < oldSize; i++)
  	  for (Entry curr = oldArray[i]; curr != null; curr = curr.next)
  	    add(curr.key, curr.value);
  }
     
  private boolean isPrime(int n) {
    if (n <= 1)
      return false; 	
    if (n == 2 || n == 3)
      return true;
    if (n % 2 == 0)
      return false;
    for (int i = 3; i * i <= n; i += 2)
      if (n % i == 0) return false;
    return true;
  }
  
  private int nextPrime(int n) {
  	if (n < 3) return 3; 
    if (n % 2 == 0) n++;
    while (!isPrime(n)) n += 2;
    return n;
  }
  
  public String toString() {
    String buf = "";
    for (int i = 0; i < array.length; i++) {
      buf += i + ": ";
      for (Entry curr = array[i];
          curr != null; curr = curr.next)
        buf += curr + " ";
      buf += "\n";;
    }
    return buf;
  }                    
}
